import functools


class Solution(object):
    def strangePrinter(self, s):
        n = len(s)

        @functools.cache
        def dfs(i, j):
            if i > j:
                return 0
            if i == j:
                return 1
            else:
                min_val = dfs(i, j - 1) + 1
                for k in range(i, j):
                    if s[j] == s[k]:
                        min_val = min(min_val, dfs(i, k) + dfs(k + 1, j - 1))
                return min_val

        return dfs(0, n - 1)
